#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct note
{
	int data;
	struct note *left, *right;
} binary_note_t;

binary_note_t *getnewNote(int key)
{
	binary_note_t *newnote = (binary_note_t *)malloc(sizeof(binary_note_t));
	if (newnote == NULL) return NULL;
	
	newnote->data = key;
	newnote->left = NULL;
	newnote->right = NULL;
	
	return newnote;
}

binary_note_t *insert(binary_note_t *root, int key)
{
	if (root == NULL) return getnewNote(key);
	
	if (rand() % 2) root->left = insert(root->left, key);
	else root->right = insert(root->right, key);
	
	return root;
}

#define MAX_NODE 10
binary_note_t *queue[MAX_NODE + 5];
int head, tail;

void bfs(binary_note_t *root)
{
	if (root == NULL) return ;
	head = tail = 0;
	queue[tail++] = root;
	
	while (head < tail)
	{
		binary_note_t *note = queue[head];
		printf("\nnode : %d\n", root->data);		
		if (note->left)
		{
			queue[tail++] = note->left;
			printf("\t%d->%d (left)\n", root->data, root->left->data);		
		}
		if (note->right)
		{
			queue[tail++] = note->right;
			printf("\t%d->%d (right)\n", root->data, root->left->data);
		}
		head++;
	}
	return ;
}

int tot = 0;
void dfs(binary_note_t *root)
{
	if (root == NULL) return ;
	int start, end;
	tot += 1;
	start = tot;
	if (root->left) dfs(root->left);
	if (root->right) dfs(root->right);
	tot += 1;
	end = tot;
	printf("%d : [%d, %d]\n", root->data, start, end);
	return ;
}

void clear(binary_note_t *root)
{
	if (root == NULL) return ;
	clear(root->left);
	clear(root->right);
	
	free(root);

	return ;
}


int main(void)
{
    srand(time(0));
    binary_note_t *root = NULL;
    for (int i = 0; i < MAX_NODE; i++)
	{
        root = insert(root, rand() % 100);
    }
    bfs(root);
    dfs(root);
    
    return 0;
}

